CF147B Smile House

貌似 @DDF_Van 大佬的标程过不了 ， 有些题解用的二分会多一个$log_n$，那就补一发倍增题解吧。

Solution 1

设$dp[s][i][j]$表示走了不多于$s$条边，$i \to j$的最大边权(走不通为极小值)

如果有$u \to v$的一条边，那么$dp[1][u][v]=w$（$w$为这条边的权值）

那么转移为：

$dp[s][i][j]=max(dp[s-1][i][k]+dp[1][j][k])$

显然，如果存在$dp[k][i][i](k \le s)$ ， 那么答案为$k$。

时间复杂度$\Theta(n^4)$ , 70分。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 300;
int n , m , x , y , z , w , Ans;
int dp[ MAXN + 5 ][ MAXN + 5 ][ MAXN + 5 ];

int main( ) {
    memset( dp , 0xcf , sizeof( dp ) );

    scanf("%d %d",&n,&m);
    for( int i = 1 ; i <= m ; i ++ ) {
        scanf("%d %d %d %d",&x,&y,&z,&w);
        dp[ 1 ][ x ][ y ] = z;
        dp[ 1 ][ y ][ x ] = w;
    }
    for( int s = 2 ; s <= n ; s ++ ) {
        for( int k = 1 ; k <= n ; k ++ )
            for( int i = 1 ; i <= n ; i ++ ) {
                for( int j = 1 ; j <= n ; j ++ )
                    dp[ s ][ i ][ j ] = max( dp[ s ][ i ][ j ] , dp[ s - 1 ][ i ][ k ] + dp[ 1 ][ k ][ j ] );
                if( dp[ s ][ i ][ i ] > 0 ) {
                    Ans = s;
                    goto there;
                }
            }     
    } 
    there:;
    printf("%d",Ans);
    return 0;
}

Solution 2

我们有必要重新定义一下$dp$转移式，设$dp[s][i][j]$表示走了不超过$2^s$条边，$i \to j$的最大边权(走不通为极小值)。

那么转移为：

$dp[s][i][j]=max(dp[s-1][i][k]+dp[s-1][k][j])$

我们可以用$\Theta(n^3log_n)$预处理求出。

在我们计算答案时，我们用类似倍增爬树的方法。

先尝试走了不超过$2^s$条边从$x$走到了$y$的最小边权和 , $s$从大到小枚举。

1.如果没有正环，说明答案大于$2^s$ , 那么下一步增加$2^{s-1}$条边

转移时需用到上一次状态，用$now[i][j]$记录上一次尝试$i \to j$的最长路径。

2.如果有正环，说明答案小于等于$2^s$，那么下一步尝试$2^{s-1}$条边

倍增时间复杂度为$\Theta(n^3log_n)$ , 总时间复杂度$\Theta(n^3log_n)$。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 300 , MAXK = 10;
int n , m , x , y , z , w , Ans;
int dp[ MAXK + 5 ][ MAXN + 5 ][ MAXN + 5 ];
int tmp[ MAXN + 5 ][ MAXN + 5 ] , now[ MAXN + 5 ][ MAXN + 5 ];

int main( ) {
    memset( now , 0xcf , sizeof( now ) );
    memset( dp , 0xcf , sizeof( dp ) );

    scanf("%d %d",&n,&m);
    for( int i = 1 ; i <= m ; i ++ ) {
        scanf("%d %d %d %d",&x,&y,&z,&w);
        dp[ 0 ][ x ][ y ] = z;
        dp[ 0 ][ y ][ x ] = w;
    }
    for( int i = 1 ; i <= n ; i ++ )
        now[ i ][ i ] = 0 , dp[ 0 ][ i ][ i ] = 0;
    
    for( int s = 1 ; s <= MAXK ; s ++ )		//预处理
        for( int k = 1 ; k <= n ; k ++ )
            for( int i = 1 ; i <= n ; i ++ )
                for( int j = 1 ; j <= n ; j ++ )
                    dp[ s ][ i ][ j ] = max( dp[ s ][ i ][ j ] , dp[ s - 1 ][ i ][ k ] + dp[ s - 1 ][ k ][ j ] );
    
    for( int s = MAXK ; s >= 0 ; s -- ) {
        memset( tmp , 0xcf , sizeof( tmp ) );

        for( int k = 1 ; k <= n ; k ++ )	//转移
            for( int i = 1 ; i <= n ; i ++ )
                for( int j = 1 ; j <= n ; j ++ )
                    tmp[ i ][ j ] = max( tmp[ i ][ j ] , now[ i ][ k ] + dp[ s ][ k ][ j ] );

        bool f = 0;
        for( int i = 1 ; i <= n ; i ++ )
            if( tmp[ i ][ i ] > 0 ) {
                f = 1;
                break;
            }
        if( f ) continue;	//有正环
        else {				//无正环
            for( int i = 1 ; i <= n ; i ++ )
                for( int j = 1 ; j <= n ; j ++ )
                    now[ i ][ j ] = tmp[ i ][ j ];
            Ans += 1 << s;
        }
    }
    printf("%d\n", Ans >= n ? 0 : Ans + 1 );
    return 0;
}